package woa;

import java.util.*;

/**
 * @author wangpeng
 * @date 2023/8/15 15:22
 */
public class RandomizedSet {

    private int[] container;
    private int tail = 0;
    private Map<Integer, Integer> hashtable;

    public RandomizedSet() {
        container = new int[200010];
        hashtable = new HashMap<>(200010);
    }

    /**
     * 当元素 val 不存在时，向集合中插入该项，并返回 true ；否则，返回 false
     *
     * @param val
     * @return
     */
    public boolean insert(int val) {
        if (hashtable.containsKey(val)) {
            return false;
        }
        hashtable.put(val, tail);
        container[tail++] = val;
        return true;
    }

    /**
     * 当元素 val 存在时，从集合中移除该项，并返回 true ；否则，返回 false
     *
     * @param val
     * @return
     */
    public boolean remove(int val) {
        Integer i = hashtable.remove(val);
        if (i == null) {
            return false;
        }
        tail--;
        container[i] = container[tail];
        if (tail > 0) {
            hashtable.put(container[i], i);
        }
        return true;
    }

    /**
     * 随机返回现有集合中的一项（测试用例保证调用此方法时集合中至少存在一个元素）。每个元素应该有 相同的概率 被返回
     *
     * @return
     */
    public int getRandom() {
        Random random = new Random();
        int randomNumber = random.nextInt(tail);
        return container[randomNumber];
    }

    public static void main(String[] args) {
        RandomizedSet randomizedSet = new RandomizedSet();
        System.out.println(randomizedSet.insert(1));
        System.out.println(randomizedSet.getRandom());
        System.out.println(randomizedSet.remove(1));
    }

    /**
     * Your RandomizedSet object will be instantiated and called as such:
     * RandomizedSet obj = new RandomizedSet();
     * boolean param_1 = obj.insert(val);
     * boolean param_2 = obj.remove(val);
     * int param_3 = obj.getRandom();
     */
}
